package string;

import org.junit.Test;

/**
 * @Description
 * @Author Firenut
 * @Date 2023-05-06 00:30
 */
public class T43_multiply {

    @Test
    public void test() {
        System.out.println(multiply("2", "3"));
    }

    // 法1: nums2的每一位和nums1做相乘,注意nums2除了最后一位不需要补0
    // 其他位都需要补0,比如第2位需要补1个0,第3位需要补2个0
    // 保留每一位和nums1的计算结果,最后将各个结果加起来就得到相乘结果了
    // 这里涉及到字符串的相加

    // 法2: 优化
    // 法1是计算完结果之后再逐一相加,如果能在循环中就顺便计算结果,则可以提高效率
    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }
        StringBuilder ans = new StringBuilder();
        // 相乘结果的位数最大为 num1.length+num2.length,即首位有可能是0
        int num[] = new int[num1.length() + num2.length()];
        for (int i = num1.length() - 1; i >= 0; i--) {
            int n1 = num1.charAt(i) - '0';
            for (int j = num2.length() - 1; j >= 0; j--) {
                int n2 = num2.charAt(j) - '0';
                int sum = num[i + j + 1] + n1 * n2;
                // =
                num[i + j + 1] = sum % 10;
                // +=
                num[i + j] += sum / 10;
            }
        }

        for (int i = 0; i < num.length; i++) {
            if (i == 0 && num[i] == 0) {
                continue;
            }
            ans.append(num[i]);
        }
        return ans.toString();
    }
}
